package LeetCode_力扣;
//234. 回文链表

//要求：给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。
// 如果是，返回 true ；否则，返回 fal

/**
 * 思路一： 开辟一个新链表，链表的内容就是元链表的反转。
 *  然后两个链表依次比较到 null 如果全部都相等，就说明是回味链表。
 */

/*

public class isPalindrome_234 {

    //头插法
    public ListNode reverseList(ListNode head) {
        ListNode dummyHead = new ListNode();

        while(head != null){
            ListNode node = new ListNode(head.val);//每次的新节点
            node.next = dummyHead.next;
            dummyHead.next = node;

            head = head.next;
        }

        return dummyHead.next;
    }

    public boolean isPalindrome(ListNode head) {

        ListNode p1 = reverseList(head);
        ListNode p2 = head;

        while(p1 != null || p2 != null){

            if(p1.val != p2.val){
                return false;
            }
            p1 = p1.next;
            p2 = p2.next;
        }

        return true;
    }
}

 */

/**
 * 思路二：反转链表的中间部分。可以先用之前的快慢指针找到链表
 * 的中间节点位置，然后在这个节点往后的链表进行反转，然后依次比较
 *
 */

/*

public class isPalindrome_234 {
    public boolean isPalindrome(ListNode head) {

        //先找到中间节点的地址
        ListNode prve = middleNode(head);
        //反转链表中间位置及以后的链表
        ListNode node = reverseList(prve);

        //这里的条件也可以设置成 node ！= null
        //比如是 1~5，虽然说它中间节点反转的节点多一个，
        //但 头链表的2后面还是连接在那个中间节点 3 上面的
        while(head != prve){

            if(head.val != node.val){
                return false;
            }
            head = head.next;
            node = node.next;
        }
        return true;
    }

    //三指针反转链表
    public ListNode reverseList(ListNode head) {

        ListNode prve = null;//因为要让第一个节点指向null
        ListNode cur = head;

        while(cur != null){
            ListNode next = cur.next;//记录下一个节点的地址，不然等会反转就找不到了
            cur.next = prve;
            prve = cur;//移动一位
            cur = next;//移位移位
        }
        return prve;
    }
    //返回链表的中间节点地址，用的是快慢指针的方法
    public ListNode middleNode(ListNode head) {

        ListNode slow = head;
        ListNode fast = head;

        //只有还有下一个节点存在，指针就可以走两步不报错，
        //一步走到最后节点上，二步走到 null 不影响。
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

}

 */




/*

public class isPalindrome_234 {
    public boolean isPalindrome(ListNode head) {

    }
}

 */




//class ListNode {
//    int val;
//    ListNode next;
//
//    ListNode() {
//    }
//
//    ListNode(int val) {
//        this.val = val;
//    }
//
//    ListNode(int val, ListNode next) {
//        this.val = val;
//        this.next = next;
//    }
//}
